package com.gjy.ds.sort_search;

/**
 * @author 宫静雨
 * @version 1.0
 * @since 2022-12-15 14:55:08
 */
public class Sort {

    /**
     * 将数组中的 i 和 j 位置元素互换
     *
     * @param array 待交换元素的数组
     * @param i     待交换的位置
     * @param j     待交换的位置
     */
    public void swap(int[] array, int i, int j) {
        array[i] = array[i] ^ array[j];
        array[j] = array[i] ^ array[j];
        array[i] = array[i] ^ array[j];
    }

    /**
     * 冒泡排序 - 初级
     *
     * @param array 待排序的数组
     */
    public void bubble0(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    swap(array, i, j);
                }
            }
        }
    }

    /**
     * 冒泡排序 - 改进
     *
     * @param array 待排序的数组
     */
    public void bubble1(int[] array) {
        boolean flag = true;
        for (int i = 1; i < array.length && flag; i++) {
            flag = false;
            for (int j = array.length - 1; j >= i; j--) {
                if (array[j - 1] > array[j]) {
                    swap(array, j - 1, j);
                    flag = true;
                }
            }
        }
    }

    /**
     * 简单选择排序
     *
     * @param array 待排序的数组
     */
    public void select(int[] array) {
        int min;
        for (int i = 0; i < array.length; i++) {
            min = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[min] > array[j]) {
                    min = j;
                }
            }
            if (i != min) {
                swap(array, i, min);
            }
        }
    }

    /**
     * 直接插入排序
     *
     * @param array 待排序的数组
     */
    public void insert(int[] array) {
        int temp;
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                temp = array[i];
                for (int j = i; j >= 0; j--) {
                    if (j > 0 && array[j - 1] > temp) {
                        array[j] = array[j - 1];
                    } else {
                        array[j] = temp;
                        break;
                    }
                }
            }
        }
    }

    /**
     * 希尔排序
     *
     * @param array 待排序的数组
     */
    public void shell(int[] array) {
        // i 步长
        for (int i = array.length / 2; i > 0; i /= 2) {
            // 对同一个步长区间进行比较
            for (int j = i; j < array.length; j++) {
                int v = array[j];
                int k;
                // 对步长区间中具体的的元素进行比较
                for (k = j - i; k >= 0 && array[k] > v; k -= i) {
                    // k 为左区间的取值   k+i 为右区间与左区间的对应值
                    array[k + i] = array[k];
                }
                // 此时 i 为负数, k+i 为左区间上的初始交换值
                array[k + i] = v;
            }
        }
    }

    /**
     * 快速排序
     *
     * @param array 待排序的数组
     */
    public void quick(int[] array, int low, int high) {
        if (low < high) {
            int partition = partition(array, low, high);
            quick(array, low, partition - 1);
            quick(array, partition + 1, high);
        }
    }

    private int partition(int[] array, int low, int high) {
        // 取最后一个元素作为中心元素
        int pivot = array[high];
        // 定义指向比中心元素大的指针，首先指向第一个元素
        int pointer = low;
        // 遍历数组中的所有元素，将比中心元素大的放在右边，比中心元素小的放在左边
        for (int i = low; i < high; i++) {
            if (array[i] <= pivot) {
                // 将比中心元素小的元素和指针指向的元素交换位置
                // 如果第一个元素比中心元素小，这里就是自己和自己交换位置，指针和索引都向下一位移动
                // 如果元素比中心元素大，索引向下移动，指针指向这个较大的元素，直到找到比中心元素小的元素，并交换位置，指针向下移动
                int temp = array[i];
                array[i] = array[pointer];
                array[pointer] = temp;
                /*swap(array, i, pointer);*/
                pointer++;
            }
        }
        // 将中心元素和指针指向的元素交换位置
        int temp = array[pointer];
        array[pointer] = array[high];
        array[high] = temp;
        return pointer;
    }
}
